/**
 * File: graph.h
 *
 * Integrantes:
 * @author Jormar Arellano   (05-37840) <jormar.arellano@gmail.com>
 * @author Sabrina Fernández (05-38163) <sabrinamfm@gmail.com>
 */

#ifndef GRAPH_H
#define	GRAPH_H

#include "arraylist.h"

#ifdef	__cplusplus
extern "C" {
#endif

struct Vertex;
typedef struct Vertex Vertex;

/** Nodo del grafo */
struct Vertex {
    int id;					// Identificador del vertice.
	int color;				// Color del vertice.
    ArrayList *neighbors;	// Lista de vecinos.
    int saturationDegree;   // Numero de colores (diferentes) adyacentes.
    int inConflict;         // Indica si esta en conflicto.

	// ESPECIAL PARA GRASP
	int _grasp_mark_u;			// Marca u. Especial para conjunto U.
	int _grasp_Totalmark_u;		// Total vecinos marcados con u.

    int _scatter_vi;            // Indica si ya fue colocado en Vi
    int _scatter_confCombFlag;  // Uso interno de Scatter
};

/** Un grafo */
typedef struct {
	int vertex_number;			// Numero de nodos.
	int edge_number;			// Numero de vertices.
    int cost;					// Costo del grafo.
    long penaltyCost;			// Costo de penalidad del grafo.
    ArrayList *vertex;			// Arreglo de vertices.
    ArrayList *Vcolors;			// Lista de los vertices de colores. 
    ArrayList *conflictVertex;	// Vertices que estan en conflicto.
} Graph;

/**
 * Parsea un archivo de prueba, y genera un grafo nuevo.
 * @param	f_name	Nombre del archivo.
 * @return	Un grafo despues de parsearse el archivo.
 */
Graph *parser_graph(char * f_name);

/**
 * Crea un nuevo vertice.
 * @param	id Identificador del vertice.
 * @return	Un nuevo vertice.
 */
Vertex *newVertex(int id);

/**
 * Crea un vertice nuevo a partir de otro. Si se especifica true el segundo parametro, 
 * el nuevo vertice compartira los mismos vecinos que el vertice original.
 * @param	v				Vertice a clonar
 * @param	withNeighbors	True si se quieren clonar los vecinos.
 * @return	Un nuevo vertice que es clon de otro.
 */
Vertex *cloneVertex(const Vertex *v, int withNeighbors);

/**
 * Compara dos vertices por sus IDs.
 * @param	v1    Primer vertice a comparar por ID.
 * @param	v2    Segundo vertice a comparar por ID.
 * @return  -1 si v1<v2
 *			 1 si v1>v2
 *			 0 si v1=v2
 */
int compareVertexById(ArrayListValue v1, ArrayListValue v2);

/**
 * Compara dos vertices segun el numero de vertices adyacentes (vecinos).
 * @param	v1    Primer vertice a comparar segun el numero de vertices adyacentes.
 * @param	v2    Segundo vertice a comparar segun el numero de vertices adyacentes.
 * @return  -1 si v1<v2
 *			 1 si v1>v2
 *			 0 si v1=v2
 */
int compareVertexByNeighbor(ArrayListValue v1, ArrayListValue v2);

/**
 * Para Grasp. Compara vertices por cantidad de vecinos u.
 * @param	v1    Primer vertice a comparar segun cantidad de vecinos u.
 * @param	v2    Segundo vertice a comparar segun cantidad de vecinos u.
 * @return  -1 si v1<v2
 *			 1 si v1>v2
 *			 0 si v1=v2
 */
int compareVertexByGrasp_Totalu(ArrayListValue v1, ArrayListValue v2);

/**
 * Imprime un vertice del grafo.
 * @param	v	Vertice del grafo a imprimir.
 */
void printVertex(Vertex *v);

/**
 * Calcula el numero de conflictos que genera el vertice.
 * @param	v	Vertice del grafo al que se le busca el numero de conflictos.
 * @return	El numero de conflictos que tiene el vertice.
 */
int getNumConflict(Vertex *v);

/**
 * Verifica si el vertice tiene conflictos con un color. Si 
 * color == 0 verifica si el nodo tiene conflictos con su color actual.
 * @param	v		vertice al que veremos si tiene conflicto.
 * @param	color	color con el cual vamos a chequear si hay conflicto.
 * @return	1 si tiene conflictos.
 *			0 si no tiene conflictos.
 */
int vertexHasConflict(Vertex *v, int color);

/**
 * Borra un vertice.
 * @param	v	Vertice para borrar.
 */
void freeVertex(Vertex *v);

/**
 * Crea un grafo nuevo.
 * @param	vertex_number	Numero de vertices del grafo.
 * @param	edge_number		Numero de aristas del grafo.
 * @param	cost			Costo del grafo.
 * @return	Un grafo nuevo.
 */
Graph *newGraph(int vertex_number, int edge_number, int cost);

/**
 * Crea un grafo nuevo a partir de otro.
 * @param	graph	Grafo que se va a clonar.
 * @return	Un nuevo grafo igual al que se clono.
 */
Graph *cloneGraph(const Graph *graph);

/**
 * Conecta los vertices v1 y v2.
 * Esto se hace agregando las aristas (v1, v2) y (v2, v1) al grafo.
 * @param	graph	Grafo al que se le agrega la nueva arista.
 * @param	v1      Primer vertice que tiene la arista.
 * @param	v2      Segundo vertice que tiene la arista.
 */
void addEdge(Graph *graph, int v1, int v2);

/**
 * Agrega un nodo a la lista de nodos conflictivos.
 * @param	graph	Grafo que se modifica.
 * @param	v		Vertice que vamos a marcar como conflictivo.
 */
void addConflictNode(Graph *graph, Vertex *v);

/**
 * Agrega un nodo a la lista de nodos conflictivos.
 * @param	graph	Grafo que se modifica.
 * @param	v		Vertice que vamos a quitar de la lista de conflictivos.
 */
void removeConflictNode(Graph *graph, Vertex *v);

/**
 * Cambia el color de un vertice del grafo.
 * Mantiene actualizada las particiones de colores Vcolor.
 *
 * @param	graph   Grafo que se modifica.
 * @param	v		Vertice del grafo al que le cambiaremos el color.
 * @param	color	Color que se va asignar al vertice.
 */
void setColor(Graph *graph, Vertex *v, int color);

/**
 * Elimina los colores que ya no se estan usando en el grafo.
 * @param	graph	Grafo que se modifica.
 */
void removeDeadColors(Graph *graph);

/**
 * Elimina rapidamente los colores de los vertices del grafo
 */
void discolorGraph(Graph *graph);

/**
 * Calcula el grado de saturacion de un vertice.
 * @param	v	Vertice del grafo al que se le calcula el grado de saturacion.
 */
// void actualizeSaturationDegree(Vertex *v);

/**
 * Imprime un grafo completo.
 * @param	graph	Grafo a imprimir.
 */
void printGraph(Graph *graph);

/**
 * Imprime los colores del grafo unicamente.
 * @param	graph	Grafo al que solo se le imprimiran los colores.
 */
void printGraphColors(Graph *graph);

/**
 * Imprime la lista de vertices en comflictos.
 * @param	graph	Grafo al que se le imprimira la lista de vertices con conflicto.
 */
void printGraphConflicts(Graph *graph);

/**
 * Obtiene el numero de colores que se estan usando en el grafo.
 * @param	graph	Grafo al que se le busca el numero de colores actual.
 */
int getTotalColor(Graph *graph);

/**
 * Colorea el primer grafo igual que el segundo.
 * @param	g1	Grafo que vamos a colorear.
 * @param	g2	Grafo que sera copiado.
 */
void colorMatch(Graph *g1, const Graph *g2);

/**
 * Libera toda la memoria usada por un grafo.
 * @param	graph	Grafo que vamos a borrar.
 */
void freeGraph(Graph *graph);

/**
 * Verifica si la coloracion actual del grafo es una solucion admisible para 
 * el problema de coloracion.
 * @param	graph	Grafo que vamos a chequear si tiene una solucion admisible.
 * @return	1 si es admisible.
 *			0 si no es admisible.
 */
int isFeasibleSolution(Graph *graph);

/**
 * Calcula el costo de penalidad de un grafo.
 * @param	graph	Grafo al que vamos a buscar su penalidad.
 * @return	La penalidad del grafo.
 */
long penaltyCost(Graph *graph);

#ifdef	__cplusplus
}
#endif

#endif

